1. Field of the Invention
The Present invention is directed to a computer-assisted processing of a graph that comprises nodes and edges.
2. Description of the Related Art
A fast, computer-assisted determination of the shortest paths in directed or undirected graphs is required in the greatest variety of computer-assisted applications.
A number of methods for determining shortest paths are known for this purpose. An overview of known methods, for example the Moore/Pape method or of the Dijkstra algorithm as well, may be found in B. V. Cherkassky et al., Shorest Path Algorithm, Theory and Experimental Evaluation. A corresponding method, however, includes the disadvantage that nearly all nodes of the graph must be taken into consideration given start and destination nodes lying far apart in order to identify the shortest path between a prescribed starting part and a prescribed destination point.
H. P. Canibol and E. Muller, Schoner fahren, focus and P. Robke-Doerr, Pfad-Finder disclose a computer-assisted navigation system in a motor vehicle. Maps are stored in a memory of the navigation system, whereby individual locations on the map (for example, houses, railroad stations, points of interest, etc.) are represented by nodes of a graph. The connections between the locations (streets, paths, etc.) are represented by edges of the graph. The shortest or, respectively, fastest path between the starting position and the target position is determined in the navigation system for a predetermined starting position and a predetermined target position upon employment of a method for determining shortest paths.
DE 195 13 960 A1 discloses a method for imaging a graph in a memory on the basis of a plurality of depth and width searches in differing direction.
DE 196 06 010 A1 discloses a location data bank for the determination of routes within a traffic route network.
What is to be understood below by a shortest path is the cheapest path under a predetermined cost function on the edges of a graph (for example, geographical length, anticipated travel time, etc.)
The known navigation system exhibits the disadvantage that an optimized route, i.e. the shortest path between the starting position and the target position, can only be determined given extremely high calculating outlay, so that considerable computer performance must be made available given a fast processing of an order for route determination, as a result whereof the navigation system is rather expensive.
In some applications, an extremely great number of shortest paths must be identified in a predetermined network, as a result whereof the criterion of a fast determination of shortest paths acquires even significantly more significance.
Given centralized systems, a central server must service a plurality of inquires for route determination from a plurality of client navigation systems and must be able to rapidly determine a great number of shortest paths for this purpose.
The present invention is thus based on the problem of processing a graph that comprises nodes and edges such that a determination of a shortest path becomes possible faster than is possible with known methods.
The problem is solved by the method for computer-assisted processing of a graph that has nodes and edges, whereby the graph describes a structure of a technical system,
whereby the nodes are grouped into at least two regions,
whereby the following steps are implemented for each region and for at least some of the nodes of the region;
a) one node is selected as root node;
b) a tree of shortest paths is determined for the root node in the graph with the root node as root of the tree;
c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
The invention also provides an arrangement for computer-assisted processing of a graph that has nodes and edges, having a processor unit that is configured such that
the nodes are grouped into at least two regions;
the following steps are implemented for each region and for at least some of the nodes of the region:
a) one node is selected as root node;
b) a tree of shortest paths is determined for the root node in the graph having the root node as root of the tree;
c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
A graph that comprises nodes and edges is processed in the method. The nodes of the graph are grouped into at least two regions. The following steps are implemented for each region and for at least some of the nodes:
a) one node is selected as a root node;
b) a tree of shortest paths in the graph with the the root node as root of the tree is determined for the root node;
c) a node of an edge of the graph is then marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
The arrangement for processing a graph that comprises nodes and edges contains a processor unit that is configured such that the following steps are implemented for each region and for at least some of the nodes of the region that are grouped into at least two regions:
a) a node is selected as the root node;
b) a tree of shortest paths in the graph with the root node as the root of the tree is determined for the root node;
c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
The shortest path can be contained in the tree of shortest paths or can be contained in a further shortest path to the root node that is not in the tree of shortest paths.
Due to this extremely simple type of pre-processing of a graph, a considerable enhancement of the determination speed of a shortest path is achieved in the determination of shortest paths in the processed graph.
Any desired method for determining shortest paths, for example the Moore/Pape method or the Dijkstra algorithm as well in the respective application, bidirectionally and well, with or without target alignment via remaining path length estimation or any other method for determining shortest paths can be utilized for calculating the shortest paths in the respective application as well as in the pre-processing, i.e. in the method for processing the graph.
The substantial saving in calculating time in the determination of shortest paths as a result of the pre-processing of the invention also makes it possible to equip the navigation system with substantially less computer power, so that the costs of the navigation system can be substantially reduced.
Developments of the invention provide that the method steps a) through c) are implemented for all nodes of the respective region. The marking ensues by allocation of a binary value to the node in the edge of the respective region. The nodes are grouped into a plurality of regions in one embodiment. In a preferred development, a shortest path between a predetermined starting node and a predetermined target node is determined upon employment of the marked nodes. Specifically, the following steps are implemented for determining the shortest path between the starting node and the target node: a starting region is determined and stored, the starting node being grouped thereto; a target region is determined and stored, the target node being grouped thereto; only those edges are taken into consideration in the determination of the shortest path proceeding from the starting node for which the following is valid; a first node of the edge is marked for the target region proceeding from the starting node in the starting region, and a second node of the edge is marked for the starting region proceeding from the starting node in the starting region. In further detail, the following steps are implemented for the determination of the shortest path between the starting node and the target node: only those edges for which the following applies are taken into consideration in the determination of the shortest path proceeding from the target node: a first node of the edge is marked for the starting region proceeding from the target node in the target region, and a second node of the edge is marked for the target region proceeding from the target node in the target region. The method may be utilized for determining roots between a starting location and a target location of a digitalized map in a computer-assisted navigation system, whereby the content of the map is described by the graphs. In one embodiment, the Moore/Pape method is utilized for the determination of a shortest path.
The apparatus of the invention is also further defined, wherein the processor unit is configured such that the method steps a) through c) are implemented for all nodes of the respective region. The processor unit is configured such that the marking ensues by allocation of a binary value to the node in the edge of the respective region. The processor unit is configured such that the nodes are grouped into a plurality of regions. The processor unit is configured such that a shortest path between a predetermined starting node and a predetermined target node is determined upon employment of the marked nodes.
In one embodiment, the processor unit is configured such that the following steps are implemented for determining the shortest path between the starting node and the target node: a starting region is determined and stored, the starting node being grouped thereto; a target region is identified and stored, the target node being grouped thereto; only those edges for which the following applies are taken into consideration in the determination of the shortest path proceeding from the starting node: a first node of the edge is marked for the target region proceeding from the starting node in the starting region, and a second node of the edge is marked for the starting region proceeding from the starting node in the starting region. The processor unit is configured such that the following steps are implemented for determining the shortest path between the starting node and the target node: only those edges for which the following is valid are taken into consideration in the determination of the shortest path proceeding from the target node: a first node of the edge is marked for the starting region proceeding from the target node in the target region, and a second node of the edge is marked for the target region proceeding from the target node in the target region. For determining a shortest path between a starting node and a target node in a graph that comprises nodes and edges, the graph describes a structure of a technical system, a processor unit being provided in said arrangement that is configured such that the shortest path is determined upon employment of graphs that are processed according to the following steps: the nodes are grouped into at least two regions; the following steps are implemented for each region and for at least some of the nodes of the region: a) one node is selected as a root node; b) a tree of shortest paths is determined for the root node in the graph having the root node as a root of the tree; c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node. A digitalized map is employed, whereby the content of the map is described by a graph with nodes and edges; whereby the processed graph is employed for determining routes between a starting location and a destination location.
It is advantageous in one development of the method and of the arrangement to determine a shortest path between a predetermined starting node and a predetermined target node upon employment of the marked nodes, i.e. upon employment of the processed graph. A method for determining shortest paths with which a substantially faster determination of the shortest path is achieved is recited on the basis of this development.
In a further development of the invention, it is advantageous that the following steps are implemented for the determination of the shortest path between the starting node and the target node:
a starting region is identified and stored, the starting node being grouped thereto;
a target region is determined and stored, the target node being grouped thereto;
only those edges are taken into consideration for the determination of the shortest path proceeding from the starting node and/or proceeding from the destination node for which the following is valid:
proceeding from the starting node and/or proceeding from the target node in the starting region and/or in the target region, a first node of the edge is marked for the target region and/or for the starting region, and
proceeding from the starting node and/or proceeding from the target node in the starting region and/or in the target region, a second node of the edge is marked for the starting region and/or for the target region.
A considerable saving of calculating time in the determination of shortest paths is achieved as a result of this procedure. It should thereby be noted that the pre-processing is implemented only once dependent on the number of inquiries orxe2x80x94if it should react to modified traffic situations (traffic jams, blocked streets, etc.), is implemented at regular intervals.